/**
 * 169. 多数元素
 *
 * 【简单】
 *
 * 给定一个大小为 n 的数组 nums ，返回其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。
 * 你可以假设数组是非空的，并且给定的数组总是存在多数元素。
 *
 * 示例 1：
 * 输入：nums = [3,2,3]
 * 输出：3
 *
 * 示例 2：
 * 输入：nums = [2,2,1,1,1,2,2]
 * 输出：2
 */

function majorityElement(nums: number[]): number {
	const threshold = Math.ceil(nums.length / 2)
	const visited = {}

	for (let i = 0; i < nums.length; i++) {
		if (!visited[nums[i]]) {
			visited[nums[i]] = 0
		}
		visited[nums[i]]++
		if (visited[nums[i]] >= threshold) {
			return nums[i]
		}
	}

	return 0
}

function majorityElement2(nums: number[]): number {
	const recursion = (start, end) => {
		if (start === end) {
			return nums[start]
		}

		const mid = Math.floor((start + end) / 2)
		const lMax = recursion(start, mid)
		const rMax = recursion(mid + 1, end)
		if (lMax === rMax) return lMax

		let lCount = 0
		let rCount = 0
		for (let i = start; i <= end; i++) {
			if (nums[i] === lMax) lCount++
			if (nums[i] === rMax) rCount++
		}

		return lCount > rCount ? lMax : rMax
	}

	return recursion(0, nums.length - 1)
}
